package com.wfs.suanfa.leet;

/**
 * 排序
 *
 * @author wfs
 * @date 2022-02-15 14:19
 * https://www.cnblogs.com/ll409546297/p/10956960.html
 * 排序算法     平均时间复杂度     最好情况    最坏情况    空间复杂度   排序方式    稳定性
 * 冒泡排序         O(n2)           O(n)        O(n2)        O(1)       in-place    稳定
 * 选择排序         O(n2)           O(n2)       O(n2)        O(1)       in-place    不稳定
 * 插入排序         O(n2)           O(n)        O(n2)        O(1)       in-place    稳定
 * 希尔排序         O(n log n)      O(n log2 n) O(n log2 n)  O(1)       in-place    不稳定
 * 归并排序         O(n log n)      O(n log n)  O(n log n)   O(n)       out-place   稳定
 * 快速排序         O(n log n)      O(n log n)  O(n2)        O(log n)   in-place    不稳定
 */
public class OrderBySuanFa {

    public static void main(String[] args) {
        int arr[] = {7, 5, 3, 2, 4, 1, 8, 9, 6};
        //冒泡
        //maopao(arr);
        //select(arr);
        //insert(arr);
        //xier(arr);
        //quickSort(arr, 0, arr.length - 1);
        mergeSort(arr,0,arr.length-1);
        System.out.println(arr);

    }

    /**
     * 冒泡
     * a、冒泡排序，是通过每一次遍历获取最大/最小值
     *
     * 　　b、将最大值/最小值放在尾部/头部
     *
     * 　　c、然后除开最大值/最小值，剩下的数据在进行遍历获取最大/最小值
     */
    private static void maopao(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * a、将第一个值看成最小值
     * <p>
     * 　　b、然后和后续的比较找出最小值和下标
     * <p>
     * 　　c、交换本次遍历的起始值和最小值
     * <p>
     * 　　d、说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值。
     */
    private static void select(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    index = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }

    /**
     * 插入排序
     * a、默认从第二个数据开始比较。
     * <p>
     * b、如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡猾）。否则，退出循环
     * <p>
     * c、说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出。
     */
    private static void insert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 希尔排序
     * a、基本上和插入排序一样的道理
     * <p>
     * b、不一样的地方在于，每次循环的步长，通过减半的方式来实现
     * <p>
     * c、说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。
     */
    private static void xier(int[] arr) {
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k > 0 && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
    }

    /**
     * 快排
     * a、确认列表第一个数据为中间值，第一个值看成空缺（低指针空缺）。
     * <p>
     * 　　b、然后在剩下的队列中，看成有左右两个指针（高低）。
     * <p>
     * 　　c、开始高指针向左移动，如果遇到小于中间值的数据，则将这个数据赋值到低指针空缺，并且将高指针的数据看成空缺值（高指针空缺）。
     * 然后先向右移动一下低指针，并且切换低指针移动。
     * <p>
     * 　　d、当低指针移动到大于中间值的时候，赋值到高指针空缺的地方。然后先高指针向左移动，并且切换高指针移动。
     * 重复c、d操作。
     * <p>
     * 　　e、直到高指针和低指针相等时退出，并且将中间值赋值给对应指针位置。
     * <p>
     * 　　f、然后将中间值的左右两边看成行的列表，进行快速排序操作
     */
    private static void quickSort(int[] arr, int low, int hight) {
        if (hight - low < 1) {
            return;
        }
        int key = arr[low];
        //数组中比key小的放在左边，比key大的放在右边，key值下标为i
        int i = low;
        int j = hight;
        while (i < j) {
            //j向左移，直到遇到比key小的值
            while (arr[j] >= key && i < j) {
                j--;
            }
            //i向右移，直到遇到比key大的值
            while (arr[i] <= key && i < j) {
                i++;
            }
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[low] = arr[i];
        arr[i] = key;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, hight);


        /*
        太过于累赘
        if (hight-low<1){
            return;
        }
        //标记，从高指针开始，还是低指针 默认高指针
        boolean flag=true;
        //记录指针的起始位置
        int start=low;
        int end=hight;
        //默认中间为低指针的第一个值
        int midValue=arr[low];
        while (true){
            //高指针移动
            if (flag){
                if (arr[hight]>midValue){
                    hight--;
                }else if (arr[hight]<midValue){
                    arr[low]=arr[hight];
                    low++;
                    flag=false;
                }
            }else {
                if (arr[low]<midValue){
                    low++;
                }else if (arr[low]>midValue){
                    arr[hight]=arr[low];
                    hight--;
                    flag=true;
                }
            }
            if (low==hight){
                arr[low]=midValue;
                break;
            }
            quickSort(arr,start,low-1);
            quickSort(arr,low+1,end);*/
    }

    /**
     * 归并排序
     * 　a、将列表按照对等的方式进行拆分
     * <p>
     * 　　b、拆分小最小快的时候，在将最小块按照原来的拆分，进行合并
     * <p>
     * 　　c、合并的时候，通过左右两块的左边开始比较大小。小的数据放入新的块中
     * <p>
     * 　　d、说明：简单一点就是先对半拆成最小单位，然后将两半数据合并成一个有序的列表
     */
    private static void mergeSort(int[] arr, int start, int end) {
        if (end - start <= 0) {
            return;
        }
        //再次拆分
        mergeSort(arr, start, (start + end) / 2);
        mergeSort(arr, (start + end) / 2 + 1, end);
        //记录开始、结束位置
        int left = start;
        int right = (start + end) / 2 + 1;
        //记录每个小单位的排序结果
        int index = 0;
        int[] result = new int[end - start + 1];
        //如果拆分后的两块数据 都还在
        while (left <= (start + end) / 2 && right <= end) {
            //比较两块数据的大小，然后赋值，并且移动下标
            if (arr[left] <= arr[right]) {
                result[index] = arr[left];
                left++;
            } else {
                result[index] = arr[right];
                right++;
            }
            //移动单位记录的下标
            index++;
        }
        //当某一块不存在了
        while (left<=(start+end)/2 || right<=end){
            //直接赋值记录下标
            if (left<=(start+end)/2){
                result[index]=arr[left];
                left++;
            }else {
                result[index]=arr[right];
                right++;
            }
            index++;
        }
        //最后将新的数据赋值给原来的列表，并且对应分块后的下标
        for (int i=start;i<=end;i++){
            arr[i]=result[i-start];
        }

    }


}
